\subsection{Idee \buchmann{13.1}}

Elektronische Dokumente wollen nicht nur verschlüsselt, sondern auch signiert werden.
Digitale Signaturen ermöglichen eine Kontrolle der Urheberschaft und haben eine ähnliche Funktion wie Unterschriften.
Will Alice ein Dokument $m$ signieren, berechnet sie aus dem Dokument und ihrem privaten Schlüssel \textit{Privatkey} die Signatur $s(Privatkey,m)$.
Unter Verwendung des öffentlichen Schlüssels \textit{Publickey} kann jeder verifizieren, dass die Signatur korrekt ist.

\subsection{RSA-Signaturen \buchmann{13.3}}

Das RSA-Verfahren kann zur Erzeugung digitaler Signaturen verwendet werden. Alice signiert ein Dokument $m$, indem sie ihr Entschlüsselungsverfahren
auf das Dokument anwendet. Bob verifiziert die Signatur, indem er darauf das Verschlüsselungsverfahren anwendet und prüft, ob sich daraus das Dokument $m$ ergibt.



\subsubsection{Schlüsselerzeugung}

Die Schlüsselerzeugung funktioniert genauso wie beim RSA-Verschlüsselungsverfahren.

\begin{enumerate}

\item Zwei Primzahlen $p$ und $q$ auswählen. Die Primzahlen sollten möglichst gleich groß,
	zufällig und gleichverteilt gewählt werden. Manchmal wird zusätzlich verlangt, dass $p$ und $q$ so
	gewählt werden, dass bekannte Faktorisierungsalgorithmen kein leichtes Spiel haben.

\item Den RSA-Modul $n = p \cdot q$ ausrechnen.

\item Den Verschlüsselungsexponenten  $e \in \mathbb{N}$ mit $1 < e < (p - 1) \cdot (q - 1)$ und $gcd(e, (p - 1) \cdot (q - 1)) = 1$ auswählen. Hieraus folgt,
	dass $e$ ungerade ist.

\item Den Entschlüsselungsexponenten $d \in \mathbb{Z}$ mit $1 < d < (p - 1) \cdot (q - 1)$ und $d \cdot e \equiv 1 \tmod (p - 1) \cdot (q - 1)$ berechnen

\end{enumerate}


\subsubsection{Erzeugung der Signatur}

Alice signiert eine Zahl $m\in\lbrace0,1,\ldots,n-1\rbrace$. Hierfür berechnet Alice die Signatur $s$ mit

$$s=m^{d}\tmod{n}$$

\subsubsection{Verifikation}

Bob will die Signatur $s$ verifizieren. Er besorgt sich den öffentlichen Schlüssel $(n,e)$ von Alice und berechnet

$$m=s^{e}\tmod{n}$$

Bob kennt jetzt den Text $m$. Da er ihn aus der Signatur $s$ gewonnen hat, weiß er, dass $s$ die Signatur von $m$ ist. Er braucht $m$ vorher nicht zu kennen und ist sich sicher,
dass Alice die Signatur $s$ erzeugt hat, da sie die RSA-Entschlüsselung von $m$ ist. Die Verifikation kann jeder durchführen, der den öffentlichen Schlüssel $(n,e)$ von Alice kennt.

\textbf{Beispiel}

Alice wählt $p=11,q=23,e=3$. Daraus ergibt sich $n=253,d=147$. Der öffentliche Schlüssel von Alice ist $(253,3)$, ihr geheimer Schlüssel $147$. \\\\
Alice möchte an einem Geldautomaten Geld abheben und den Betrag von 111 Euro signieren. Dazu berechnet sie $s=111^{147}\tmod{253}=89 $. Der Geldautomat erhält $s=89$
und berechnet $m=s^{3}\tmod{253}=111$. Der Automat weiß, dass Alice 111 Euro abheben will und kann das Dritten gegenüber beweisen.


\subsection{Sicherheit \buchmann{13.2}}

Ein Signaturverfahren kann nur sicher sein, wenn es unmöglich ist, in vertretbarer Zeit (polynomieller Zeit) aus den öffentlich
verfügbaren Informationen, insbesondere aus den öffentlichen Schlüsseln, den privaten Schlüssel der Nutzer zu berechnen. Die heute bekannten
Signaturverfahren beruhen auf schwer zu lösenden Berechnungsproblemen der Zahlentheorie. Bewährte Signaturverfahren können durch eine gute Idee, z.B.
mit einem Quantencomputer, unsicher werden.

\subsubsection{No-Message-Modell}

Ein Angreifer kann versuchen, ohne Kenntnis des geheimen Signaturschlüssels \textit{Privatkey} eine gültige Signatur zu berechnen, für das der legitime Signierer keine Signatur
erstellt hat. Man spricht von \textit{existientieller Fälschung}.

\begin{enumerate}

\item Der Angreifer besorgt sich den Verifikationsschlüssel \textit{Publickey} von Alice.

\item Unter Verwendung des Verifikationsschlüssels berechnet der Angreifer eine Nachricht $x$ und eine gültige Alice-Signatur für $x$.

\end{enumerate}

Ein Angreifer kann das Dokument, für das er eine Signatur berechnet, in Abhängigkeit vom öffentlichen Schlüssel berechnen, ohne dieses vorzuwählen.
Das Ergebnis ist eine gültige Signatur für einen beliebigen Text.

\subsubsection{Chosen-Message-Modell}

Der Angreifer kennt bereits andere gültige Signaturen oder lässt sich zunächst selbst gewählte Dokumente signieren, um daraus eine neue Signatur zu erzeugen.
Der Angreifer kann die Auswahl der Dokumente, die Alice für ihn signiert, an die Berechnung, die er durchführt, anpassen.

\begin{enumerate}

\item Der Angreifer besorgt sich den Verifikationsschlüssel \textit{Publickey} von Alice.

\item Unter Verwendung des Verifikationsschlüssels berechnet der Angreifer ein Dokument $x$ und eine gültige Alice-Signatur $s$ für $x$. Während
der Berechnung von $x$ und $s$ kann der Angreifer jederzeit Nachrichten seiner Wahl von Alice signieren lassen. Die Nachrichten müssen nur verschieden von $x$ sein.

\end{enumerate}


\subsection{Angriffe \buchmann{13.3.4}}

\begin{enumerate}

\item Zu Beginn besorgt sich Bob den öffentlichen Schlüssel $(n,e)$ von Alice. Gelingt es Angreifer Oskar, Bob seinen eigenen öffentlichen Schlüssel als den 
Schlüssel von Alice unterzuschieben, kann er danach Signaturen erzeugen, die Bob als Signaturen von Alice erkennt. Für Bob ist es wichtig, dass er den authentischen
öffentlichen Schlüssel von Alice hat. Er muss sich von der Authentizität des öffentlichen Schlüssels z.B. durch \textit{Trustcenter} überzeugen können. 

\item Ein anderen Angriff funktioniert so: Oskar wählt eine Zahl $s\in\lbrace0,\ldots,n-1\rbrace$ und behauptet, $s$ sei eine RSA-Signatur von Alice. Wer die Signatur verifizieren will,
berechnet $s=m^{d}\tmod{n}$ und glaubt, Alice habe $m$ signiert. Dies ist eine \textit{No-Message-Attack}. Ist $m$ ein sinnvoller Text, wurde Alice die Signatur dieses sinnvollen Textes untergeschoben.

\textbf{Beispiel}\\
Sei $p=11,q=23,e=3$. Daraus folgt $n=253,d=147$.\\\\
Oskar möchte vom Konto von Alice Geld abheben. Er schickt einfach $s=123$ an den Geldautomaten, der $m=123^{3}\tmod{253}=52$. Er glaubt, dass Alice 117 Euro abheben will, obwohl Alice die 117 Euro
nie unterschrieben hat.

\item Eine weitere Gefahr beim Signieren mit RSA kommt daher, dass das RSA-Verfahren multiplikativ ist. Sind $m\textsubscript{1},m\textsubscript{2}\in\lbrace0,\ldots,n-1\rbrace$ und sind $s\textsubscript{1}=m\textsubscript{1}^{d}\tmod{n}$
und $s\textsubscript{2}=m\textsubscript{2}^{d}\tmod{n}$ die Signaturen von $m\textsubscript{1}$ und $m\textsubscript{1}$, dann ist

$$s=s\textsubscript{1}s\textsubscript{2}\tmod{n}=(m\textsubscript{1},m\textsubscript{2})^{d}\tmod{n}$$

die Signatur von $m=m\textsubscript{1}m\textsubscript{2}$. Aus zwei gültigen Signaturen kann leicht eine dritte gültige Signatur generiert werden.\\\\
Nutzt der Angreifer die Multiplikativität aus, kann er mit einem \textit{Chosen-Message-Angriff} jede Signatur fälschen.
Soll eine Nachricht $m\in\lbrace0,\ldots,n-1\rbrace$ signiert werden, wählt der Angreifer eine von $m$ verschiedene Nachricht $m\textsubscript{1}\in\lbrace0,\ldots,n-1\rbrace$
mit $gcd(m\textsubscript{1},n)=1$. Er berechnet

$$ m=mm\textsubscript{1}^{-1}\tmod{n} $$

wobei $m\textsubscript{1}^{-1}$ das Inverse von $m\textsubscript{1}\tmod{n}$ ist. Der Angreifer lässt sich die beiden Nachrichten $m\textsubscript{1}$ und $m\textsubscript{2}$ signieren und
erhält die beiden Signaturen $s_1$ und $s_2$, mit denen er $ s=s\textsubscript{1}s\textsubscript{2}\tmod{n}$ von $m$ berechnen kann. Das RSA-Signaturverfahren, wie es bis jetzt beschrieben wurde,
ist nicht sicher gegen \textit{Chosen-Message-Angriffe}.



\end{enumerate}


\subsection{Vorbeugungsmaßnahmen}

\subsubsection{Signatur von Texten mit Redundanz}

Zwei der zuvor beschriebenen Angriffe werden unmöglich, wenn nur Texte $m\in\lbrace0,1,\ldots,n-1\rbrace$ deren Binärdarstellung der Form $w\circ w$ ist mit $w\in\lbrace0,1\rbrace^{*}$.
Die Binärdarstellung besteht aus zwei gleichen Hälften, wovon die erste Hälfte der wirklich signierte Text ist. Signiert wird das komplette $w\circ w$. Die Struktur wird
mit der $Redundanzfunktion$ erzeugt.

$$R:\lbrace0,1\rbrace^{*}\to\lbrace0,1\rbrace^{*},w\mapsto R(w)= w\circ w$$


\begin{enumerate}
\item Durch die Redundanz kann keine existenzielle Fälschung (No-Message-Modell) mehr verwendet werden. Es ist unbekannt, wie man ohne Kenntnis
des privaten Schlüssels eine Signatur $s\in\lbrace0,1,\ldots,n-1\rbrace$ für die Binärentwicklung $m=s^{e}\tmod{n}$ bestimmen kann, die die Form 
$w\circ w$ hat.

\item Die Multiplikativität von RSA kann nicht mehr ausgenutzt werden. Es ist äußerst unwahrscheinlich, dass $m=m\textsubscript{1}m\textsubscript{2}\mod{n}$
eine Binärentwicklung von $w\circ w$ hat, wenn dies für beide Faktoren der Fall ist.

\end{enumerate}


\subsubsection{Signatur mit Hashwert}
Bisher wurde beschrieben, wie Texte $m$, deren Länge nicht größer ist als die Länge des RSA-Moduls $n$, signiert werden.
Beliebig lange Texte kann Alice mit einer öffentlichen Hashfunktion signieren
$$h:\lbrace0,1\rbrace^{*}\to\lbrace0,\ldots,n-1\rbrace$$
$h$ muss kollisionsresistent sein und deshalb auch eine Einwegfunktion. Die Signatur des Textes $m$ ist
$$s=h(m)^{d}\tmod{n}$$
Aus der Signatur lässt sich nur der Hashwert berechnen. Da zur Verifikation der Text $m$ benötigt wird, wird dieser zusammen mit der Signatur
an Bob gesendet. Bob berechnet $t=s^{e}\tmod{n}$ und vergleicht die Zahl mit dem Hashwert $h(m)$. Stimmen $t$ und $h(m)$ überein, ist die Signatur gültig.

\begin{enumerate}
 
\item Das Verfahren macht die existentielle Fälschung unmöglich. Wählt Oskar eine Signatur $s'$, muss er einen Text $m'$ produzieren und $(m',t')$ an Bob schicken.
Da Bob $t'=s'^{e}\tmod{n}$ berechnet und prüft ob $t'=h(m')$ ist, muss Oskar den Text $m'$ so bestimmen, dass $h(m')=t'$ gilt. Der Text $m'$ ist Urbild von $t'$ und $t'$ liegt durch $s'$ fest.
Oskar muss also ein Urbild $m'$ von $t'$ unter $h$ bestimmen. Dies kann er nicht, da $h$ eine Einwegfunktion ist.
 
\item Auch die Ausnutzung der Multiplikativität von RSA wird unmöglich. Weil $h$ eine Einwegfunktion ist, ist es unmöglich, einen Text $m'$ zu finden mit $h(m')=t=m\textsubscript{1}m\textsubscript{2}\tmod{n}$.
   
\item Oskar kann auch nicht den von Alice signierten Text $m$ durch einen anderen Text $m'$ mit gleicher Signatur ersetzen. Das Paar $(m,m')$ wäre eine Kollision von $h$ und $h$ wurde als kollisionsresistent angenommen.

\end{enumerate}
